package exercise.基础练习;

import java.util.Scanner;

/**
 * 资源限制
 * 时间限制：1.0s   内存限制：256.0MB
 * 问题描述
 * Fibonacci数列的递推公式为：F(n)=F(n-1)+F(n-2)，其中F1=F2=1。
 * <p>
 * 当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。
 * <p>
 * 输入格式
 * 输入包含一个整数n。
 * 输出格式
 * 输出一行，包含一个整数，表示Fn除以10007的余数。
 * 说明：在本题中，答案是要求Fn除以10007的余数，因此我们只要能算出这个余数即可，而不需要先计算出Fn的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余简单。
 * <p>
 * 样例输入
 * 10
 * 样例输出
 * 55
 * 样例输入
 * 22
 * 样例输出
 * 7704
 * 数据规模与约定
 * 1 <= n <= 1,000,000。
 */
public class B04_斐波那契数列求余数 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(solution(n));
    }

    /**
     * 本题用递归绝对超时，只能用迭代。
     * 迭代：空间换时间
     *
     * @param n
     * @return
     */
    private static int solution(int n) {
        if (n == 1 || n == 2){
            return 1;
        }
        int[] mods = new int[n];//存储余数
        //已知前两个是1
        mods[0] = 1;
        mods[1] = 1;
        for (int i = 2; i < mods.length; i++) {
            mods[i] = (mods[i - 1] + mods[i - 2]) % 10007;
        }
        return mods[n - 1];//返回最后一个
    }
}
